// 

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;


class Solution{
public:
    int subarraySum(vector<int> & nums, int k){

        // int count = 0;
        // for (int start = 0; start < nums.size(); ++start){

        //     int sum = 0;
        //     // 每一个不同的开头都遍历了所有可能
        //     for(int end = start; end >= 0; --end){
        //         sum += nums[end];

        //         if (sum == k){
        //             count ++;
        //         }
        //     }
        // }


        // return count;

        // @优化后的方法
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto & x : nums){
            pre += x;
            // 查找建
            if (mp.find(pre - k) != mp.end()){
                count += mp[pre - k];
            }
            // 存储前缀和，固定一个前缀和就好理解了
            mp[pre] ++ ;

        }
        return count;
    }

};
